package 程序员面试金典;

/**
 * 面试题 04.02. 最小高度树
 * 给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
 *
 * 示例:
 * 给定有序数组: [-10,-3,0,5,9],
 *
 * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
 *
 *           0
 *          / \
 *        -3   9
 *        /   /
 *      -10  5
 */
public class T04_02 {
    public TreeNode sortedArrayToBST(int[] nums) {

        return dfs(nums,0,nums.length);

    }

    private TreeNode dfs(int[] ints,int left,int right){

        if (left==right) return null;

        int mid = (left+right)/2;

        TreeNode root = new TreeNode(ints[mid]);

        root.left = dfs(ints,left,mid);
        root.right = dfs(ints,mid+1,right);

        return root;
    }

    static  class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
}
